# Графы

_Граф_ (_graph_) обычно определяется как множество точек (называемых _вершинами_ (_vertices_)) 
вместе с набором линий (называемых _ребрами_ (_edges_)), которые соединяют определенные пары вершин. 
Каждая пара вершин соединяется не более чем одним ребром. 
Две вершины называются _смежными_ (_adjacent_), если их соединяет ребро. 
Если \\(V\\) и \\(\acute{V}\\) являются вершинами и \\(n \geq 0\\), то \\((V\_{0}, V\_{1}, ... , V\_{n})\\) 
называется _путем_ длины n от вершины \\(V\\) к вершине \\(\acute{V}\\), 
если \\(V = V\_{0}\\), вершина \\(V\_{k}\\) является смежной для вершины \\(V\_{k+1}\\) для \\(0 \leq k < n\\), 
а \\(V\_{n} = \acute{V}\\). 
Путь называется _простым_ (_simple_), если различны вершины \\(V\_{0}, V\_{1}, ... , V\_{n−1}\\) 
и если различны вершины \\(V\_{1}, ... , V\_{n−1}, V\_{n}\\). 
Граф называется _связным_ (_connected_), если существует путь между любыми двумя его вершинами. 
_Циклом_ называется простой путь длиной, большей или равной трем, от некоторой вершины к ней самой.

**Код:**

В следующем коде определены классы `Vertex`, `Edge` и `Graph`, которые представляют собой неориентированный граф.

- Метод `addVertex` добавляет новую вершину в граф. Если вершина с таким же значением уже существует, 
  то возвращает текущий граф. Если вершины с таким значением нет, то создает новую вершину и добавляет ее в граф.
- Метод `addEdge` добавляет новое ребро в граф. Он проверяет, существуют ли исходная и конечная вершины в графе. 
  Если хотя бы одна из вершин не найдена, то возвращает соответствующую ошибку. 
  Если обе вершины найдены, то проверяет, существует ли уже ребро между этими вершинами. 
  Если ребро уже существует, то возвращает соответствующую ошибку. 
  Если ребра не существует, то создает новое ребро и добавляет его в граф.
- Метод `areAdjacent` проверяет, являются ли две вершины смежными (т.е., имеют ли между собой ребро). 
  Если хотя бы одна из вершин не найдена, то возвращает соответствующую ошибку. 
  Если обе вершины найдены, то проверяет, существует ли ребро между этими вершинами, и возвращает результат.
- Методы `findVertexes`, `findVertex`, `findEdge` служат для поиска вершин и ребер в графе. 

```dotty
final case class Vertex[A: Ordering](id: UUID, value: A):
  def contains(value: A): Boolean = summon[Ordering[A]].equiv(this.value, value)

final case class Edge[A](from: UUID, to: UUID, value: A)

final case class Graph[A: Ordering, B] private (
    vertices: Map[UUID, Vertex[A]],
    edges: Vector[Edge[B]]
):
  self =>

  def addVertex(value: A): Graph[A, B] =
    if vertices.exists(_._2.contains(value)) then self
    else
      val newVertex = Vertex(UUID.randomUUID(), value)
      Graph(vertices + (newVertex.id -> newVertex), edges)

  def addEdge(from: A, to: A, value: B): Either[String, Graph[A, B]] =
    for
      (fromVertex, toVertex) <- findVertexes(from, to)
      edge <- if findEdge(fromVertex.id, toVertex.id).isDefined then
        Left("Эта вершина уже содержится в графе")
      else Right(Edge(fromVertex.id, toVertex.id, value))
    yield Graph(vertices, edges :+ edge)

  def areAdjacent(from: A, to: A): Either[String, Boolean] =
    findVertexes(from, to).map(vs => findEdge(vs._1.id, vs._2.id).isDefined)

  private def findVertexes(
      from: A,
      to: A
  ): Either[String, (Vertex[A], Vertex[A])] =
    for
      fromVertex <- findVertex(from).toRight("Исходящая вершина не найдена")
      toVertex   <- findVertex(to).toRight("Конечная вершина не найдена")
    yield (fromVertex, toVertex)

  private def findVertex(value: A): Option[Vertex[A]] =
    vertices.collectFirst {
      case (id, vertex) if vertex.contains(value) => vertex
    }

  private def findEdge(from: UUID, to: UUID): Option[Edge[B]] =
    edges.find: edge =>
      edge.from == from && edge.to == to ||
        edge.from == to && edge.to == from

end Graph
```

## Свободное дерево

_Свободное дерево_ (_free tree_), или дерево без корня, определяется как связный граф без циклов.

##### Теорема

Если G — граф, то для него будут эквивалентными следующие утверждения.

- a) G — свободное дерево.
- b) G — связный граф, который при удалении произвольного ребра перестает быть связным.
- c) Если \\(V\\) и \\(\acute{V}\\) — различные вершины графа G, 
  то существует единственный простой путь от вершины \\(V\\) к вершине \\(\acute{V}\\). 
  Более того, если граф G конечен и содержит в точности n > 0 вершин, 
  следующие утверждения также будут эквивалентны утверждениям (a)–(c).
- d) G не содержит циклов и имеет n − 1 ребер.
- e) G — связный граф, который имеет n − 1 ребер.

## Ориентированный граф

Формально определим _ориентированный граф_ (_directed graph_ или _digraph_) как множество вершин и множество _дуг_ или _ребер_ (_arcs_), 
каждая из которых проходит от вершины \\(V\\) до вершины \\(\acute{V}\\). 
Если e является дугой от вершины \\(V\\) до вершины \\(\acute{V}\\), назовем V _начальной_ (_initial_) вершиной дуги e, 
а \\(\acute{V}\\) — _конечной_ (_final_) вершиной и запишем \\(V = init(e)\\), \\(\acute{V} = fin(e)\\). 
При этом возможен случай, когда \\(init(e) = fin(e)\\) (хотя при определении ребра обычного графа он исключается) 
и несколько различных дуг могут иметь одинаковые начальные и конечные вершины. 
_Степенью выхода_ (_outdegree_) вершины \\(V\\) является количество дуг, которые выходят из нее, 
а именно — число таких дуг e, что \\(init(e) = V\\). 
Аналогично _степень входа_ (_in-degree_) вершины \\(V\\) определяется как количество дуг, для которых \\(fin(e) = V\\).

Если \\(e\_{1}, e\_{2}, ... , e\_{n}\\) являются дугами (с \\(n \geq 1\\)), то будем считать,
что (\\(e\_{1}, e\_{2}, ... , e\_{n}\\)) является _ориентированным путем_ (_oriented path_) длины n 
от вершины \\(V\\) до вершины \\(\acute{V}\\), если \\(V = init(e\_{1}), \acute{V} = fin(e\_{n})\\), 
а \\(fin(e\_{k}) = init(e\_{k+1})\\) для \\(1 \leq k < n\\). 
Ориентированный путь (\\(e\_{1}, e\_{2}, ... , e\_{n}\\)) называется _простым_ (_simple_), 
если \\(init(e\_{1}), ... , init(e\{n})\\) различны и \\(fin(e\_{1}), ... , fin(e\_{n})\\) различны. 
_Ориентированный цикл_ (_oriented cycle_) — это простой ориентированный путь от некоторой вершины до нее самой.

Ориентированный граф называется _строго связным_ (_strongly connected_), 
если существует ориентированный путь от вершины \\(V\\) до вершины \\(\acute{V}\\) для любых двух вершин \\(V \neq \acute{V}\\). 
Он является _корневым_ (_rooted_), если существует хотя бы один _корень_ (_root_), 
т.е. по крайней мере одна такая вершина \\(R\\), 
при наличии которой существует ориентированный путь от \\(V\\) к \\(R\\) для всех \\(V \neq R\\). 
"Строго связный" граф всегда является "корневым", но обратное утверждение не верно. 

## Ориентированное дерево

_Ориентированное дерево_ (_oriented tree_), иногда называемое корневым деревом, 
представляет собой ориентированный граф с такой вершиной \\(R\\), что:

- a) каждая вершина \\(V \neq R\\) является начальной вершиной в точности одной дуги, которая обозначается как \\(e\[V\]\\);
- b) \\(R\\) не является начальной вершиной ни одной из дуг;
- c) \\(R\\) является корнем в указанном выше смысле 
  (т.е. для каждой вершины \\(V \neq R\\) существует ориентированный путь от \\(V\\) к \\(R\\)).

## Сбалансированный ориентированный граф

_Цепью Эйлера_ (_Eulerian circuit_) в ориентированном графе является такой ориентированный путь \\((e\_{1}, e\_{2}, ... , e\_{m})\\),
что каждая дуга ориентированного графа встречается в этом пути только один раз и \\(fin(e\_{m}) = init(e\_{1})\\).
Она представляет собой "полный обход" дуг диграфа.

Ориентированный граф называется _сбалансированным_ (_balanced_), 
если каждая вершина V имеет равные по величине степени входа и выхода, 
т.е. сколько существует ребер, для которых вершина V является начальной, 
столько же существует ребер, для которых вершина V является конечной. 
Если ориентированный граф имеет цепь Эйлера, то очевидно, что он должен быть связным и сбалансированным, 
за исключением случаев, когда он имеет _изолированные вершины_ (_isolated vertices_), 
т.е. вершины c равными нулю степенями входа и выхода.

## Теоремы

### Теорема Гуда

> Конечный ориентированный граф без изолированных вершин содержит цепь Эйлера тогда и только тогда, 
> когда он связанный и сбалансированный.

---

**Ссылки:**

- [Donald E. Knuth - The Art of Computer Programming, section 2.3.4.1 - 2.3.4.2](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
